package com.hainiu.cat.sort;

/**
 * create by biji.zhao on 2021/5/29
 */
public class ReverseList {

    private int data;
    private ReverseList next;

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ReverseList getNext() {
        return next;
    }

    public void setNext(ReverseList next) {
        this.next = next;
    }

    public ReverseList(int data) {
        this.data = data;
    }

    /**
     * 递归实现单链表的反转
     * @param head  链表元素
     * @return      新链表
     */
    private static ReverseList recursion(ReverseList head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
        // 递归至最深处找到尾节点
        ReverseList reHead = recursion(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        // 最终也返回尾节点，以便重新复制给老的node 这样实现反转效果
        return reHead;
    }

    public static void main(String[] args) {
        ReverseList one = new ReverseList(1);
        ReverseList two = new ReverseList(2);
        ReverseList three = new ReverseList(3);
        ReverseList four = new ReverseList(4);
        one.setNext(two);
        two.setNext(three);
        three.setNext(four);

        printNode(one);
//        one = recursion(one);
        one = reverse(one);
        printNode(one);
    }

    private static void printNode(ReverseList list) {
        if (list == null) {
            return;
        }
        StringBuilder builder = new StringBuilder();
        ReverseList temp = list;
        builder.append("--").append(temp.getData());
        while (temp.getNext() != null) {
            builder.append("--").append(temp.getNext().getData());
            temp = temp.getNext();
        }
        System.out.println(builder.toString());
    }

    /**
     * 循环实现单链表反转
     * @param head  单链表
     * @return      新链表  （此时记住，只需要返回头元素即可，毕竟入参也是如此）
     */
    public static ReverseList reverse(ReverseList head) {
        ReverseList pre = null;
        ReverseList next;
        while (head != null) {
            // 先借助中间变量缓存当前节点指针域（即把下一个节点先存在这个变量中）
            next = head.getNext();
            // 将当前节点的下一个节点设置为前一个节点 （第一次为空）
            head.setNext(pre);
            // 当前节点赋值给 变量pre  （即此时pre指向当前节点）
            pre = head;
            // 游标指向下一个节点  （循环执行的动作，往后遍历整合链表）
            head = next;
        }
        return pre;
    }

}
